// NOTE: 链表是一种线性的数据结构, 动态的数据结构, 不需要处理固定容量的问题,
// 不支持快速查询, 不适合用于索引的语意的情况
// vs 数组: 支持快速查询,

// 增 删 改(不推荐改) 查 => O(n)
// 不会浪费内存空间

interface NodeInter<E> {
  e: E,
  next: NodeE | null
}

class NodeE<E = any> implements NodeInter<E> {
  public e: E
  public next: NodeE<E> | null

  constructor(e: E, next: NodeE | null) {
    this.e = e
    this.next = next
  }

  public toString() {
    return JSON.stringify(this.e)
  }
}

export class LinkedList<E = any> {

  private size: number = 0
  private head: NodeE<E> | null = null
  private dummyHead!: NodeE<E>

  constructor(arr?: E[]) {
    this.dummyHead = new NodeE(null, null) as NodeE
    if (arr && arr.length > 0) {
      this.genLinkedList(arr)
    }
  }

  public getSize(): number {
    return this.size
  }

  public isEmpty(): boolean {
    return this.size === 0
  }

  public addFirst(e: E) {
    // let node = new NodeE(e)
    this.head = new NodeE<E>(e, this.head!)
    // console.log(this.head)
    this.dummyHead.next = this.head
    this.size++
  }

  // 在链表的 index 位置添加元素
  public add(index: number, e: E) {
    if (index < 0 || index > this.size) {
      throw new Error('error index')
    }

    let prev = this.dummyHead
    for (let i = 0; i < index; i++) {
      prev = prev!.next as NodeE
    }
    prev!.next = new NodeE(e, prev!.next)
    this.size++
  }

  public get(index: number): E {
    if (index < 0 || index > this.size) {
      throw new Error('error index')
    }

    let cur = this.dummyHead.next
    for (let i = 0; i < index; i++) {
      cur = cur!.next
    }
    return cur!.e
  }

  public getFirst(): E {
    return this.get(0)
  }

  public getLast(): E {
    return this.get(this.size - 1)
  }

  public update(index: number, e: E) {
    if (index < 0 || index > this.size) {
      throw new Error('error index')
    }
    let cur = this.dummyHead.next
    for (let i = 0; i < index; i++) {
      cur = cur!.next
    }
    cur!.e = e
  }

  public contains(e: E): boolean {
    let cur = this.dummyHead.next
    while (cur) {
      if (cur.e === e) {
        return true
      }
      cur = cur.next
    }
    return false
  }

  public remove(index: number): E {
    if (index < 0 || index > this.size) {
      throw new Error('error index')
    }
    let prev = this.dummyHead
    for (let i = 0; i < index; i++) {
      prev = prev!.next as NodeE
    }
    let rmNode = prev!.next
    prev!.next = rmNode!.next
    this.head = this.dummyHead.next
    rmNode!.next = null
    this.size--
    return rmNode!.e
  }

  public removeLast() {
    return this.remove(this.size - 1)
  }

  public removeFirst() {
    return this.remove(0)
  }

  /**
   * reverse
   */
  public reverse() {
    let prev = null
    let cur = this.head
    while (cur) {
      let next = cur.next
      cur.next = prev
      prev = cur
      cur = next
    }
    this.dummyHead.next = prev
    this.head = prev
  }

  public print() {
    let cur = this.dummyHead.next
    let res = []
    while (cur) {
      res.push(`${JSON.stringify((cur.e as any).e)} => `)
      cur = cur.next
    }
    res.push('NULL')
    console.log(res.join(''))
  }

  private genLinkedList(arr: E[]) {
    this.head = new NodeE(arr[0], null) as NodeE
    this.dummyHead.next = this.head
    let cur = this.head
    for (let i = 1; i < arr.length; i++) {
      cur.next = new NodeE(arr[i], null)
      cur = cur.next
    }
  }
}
